package com.example.demo.leetcode.zuocheng.graph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给定长度和数量都为N的数组，weight,values,表示重量和价值，给定一个正数，bag，重量不超过bag的最大价值是多少
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/11 11:28
 */
public class Arr_从左往右模型2 {


    //表示单元价值
    static class Unit{
        int index;
        double unitValue;

        public Unit(int index, double unitValue) {
            this.index = index;
            this.unitValue = unitValue;
        }
    }

    //按比例处理
    public static int process(int [] weight,int [] value,int bag){

        //从大到小排序
        PriorityQueue<Unit> queue = new PriorityQueue<>(new Comparator<Unit>() {
            @Override
            public int compare(Unit o1, Unit o2) {
                return (int) (o2.unitValue - o1.unitValue);
            }
        });

        for(int i = 0 ;i<weight.length; i++){
            Unit unit = new Unit(i,value[i]/weight[i]);
            queue.add(unit);
        }

        int sumWeight = 0;
        int sumValue = 0;
        while(!queue.isEmpty()){
            Unit poll = queue.poll();
            sumWeight += weight[poll.index];
            if(sumWeight <= bag){
                sumValue += value[poll.index];
            }else{
                sumWeight -= weight[poll.index];
            }
        }
        // System.out.println(sumValue);
        return sumValue;
    }

    /**
     *
     * @param weight
     * @param value
     * @param index
     * @param alreadyW 已经背负的重量
     * @param bag 背包重量
     * @return 返回的是真正的价值
     */
    public static int process2(int [] weight,int [] value,int index,int alreadyW,int bag){

        if(bag < alreadyW){
            return -1;
        }
        if(index == weight.length){
            return 0;
        }
        // p1 表示不要当前价值后向下递归
        int p1 = process2(weight,value,index+1,alreadyW,bag);

        int p2next = process2(weight,value,index+1,alreadyW+weight[index],bag);

        int p2=-1;
        if(p2next > -1){
            p2 = p2next + value[index];
        }
        return Math.max(p1,p2);
    }

    //动态规划，通过暴力破解思考 index * alreadyW 的矩阵哪个值最大
    public static int cacheWay(int [] weight,int [] value ,int bag){
        int [][] dp = new int [value.length+1][bag+1];
        for(int index =value.length-1;index>=0;index--){
            for(int alreadyW = bag;alreadyW>=0;alreadyW--){

                int p1 = dp[index+1][alreadyW];

                int p2next = -1;
                if(alreadyW+weight[index] <= bag){
                    p2next = value[index] + dp[index+1][alreadyW+weight[index]];
                }
                dp[index][alreadyW] = Math.max(p1,p2next);

            }
        }
        return dp[0][0];
    }





    public static void main(String[] args) {
        int [] weight = {4,5,6,10,6,4,1};
        int [] value = {9,6,2,4,6,8,1};
        int value1 = process2(weight, value, 0, 0, 15);
        int value2 = process(weight,value,15);
        int value3 = cacheWay(weight,value,15);
        System.out.println("value1:"+value1+"  value2:"+value2+" value3:"+value3);

    }



}
